树状数组求区间最大值
1、在维护和查询区间和的算法中，h[x]中储存的是[x，x-lowbit(x)+1]中每个数的和 
2、在求区间最值的算法中，h[x]储存的是[x，x-lowbit(x)+1]中每个数的最大值。
求区间最值的算法中还有一个a[i]数组，表示第i个数是多少,也就是原数组。
void up(int p,int v){
    while(p<=n){
        tr[p]=max(tr[p],v);
        p+=p&(-p);
    }
}

int que(int p){
    int ans=0;
    while(p>=1){
        ans=max(ans,tr[p]);
        p-=p&(-p);
    }return ans;
}
//双条件点对统计 (i,j) j-i<=p[i]&&j-i<=p[j]
//j-i<=p[j] -> j-p[j]<=i 预处理处所有的j-p[j] 枚举到i就将满足条件的j-p[j]的j加入
//每次枚举i就统计一次 [i+1,i+p[i]] 中j的个数

单点修改区间查询会容易想到线段树或者树状数组的做法,每一次修改就是O (logn) 
树状数组//数据范围过大需要配合离散化使用
区间修改，单点查询
int n;
//t[i]表示树状数组i结点覆盖的范围和
int t[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x)
{
    return x & -x;
}

//将序列中第x个数加上k，如果序列下标从0开始那么需要整体加1
void add(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i)) t[i] += k;//注意此处的循环条件不一定是n，可能是序列的最大值
    //按照需求写
}
//查询序列前x个数的和
int ask(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) sum += t[i];
    return sum;
}

树状数组维护二阶前缀和
const int N = 500005;
// 修改差分 来维护前缀和的前缀和
// c1 为差分d c2为d*i  c3 为d*i*i
LL c1[N * 2], c2[N * 2], c3[N * 2];
LL sum(int x) {
    LL res = 0;
    for (int i = x; i > 0; i -= i & -i) {
        res += c1[i] * (x + 2) * (x + 1) - c2[i] * (2 * x + 3) + c3[i];
    }
    return res / 2;
}
void add(int x, LL d, int n) {
    for (int i = x; i <= n; i += i & -i) {
        c1[i] += d;
        c2[i] += d * x;
        c3[i] += d * x * x;
    }
}


如果有多样例清空t[]会t的话可以考虑将问题求解过程反向执行一遍
for(int j=0;j<n;j++){//求解
    ...
    add(x,1,2*n+1);
    add(y+1,-1,2*n+1);
    ...
}
for(int j=0;j<n;j++){//清空
    ...
    add(x,-1,2*n+1);
    add(y+1,1,2*n+1);
    ...
}


线段树//特别的还可以用来模拟一些区间问题，比如利用线段树进行区间染色等等

经典操作：将l-r的区间分解到线段树上若干连续的区间，不需要将线段树全建出来，所以在函数参数中增加上当前区间的左右端点
这些区间左右端点的特征是高位一段是相同的，左端点l的低位部分全0，右端点r的低位部分全1.
每分一次区间其高位就会确定一位（0/1），左边为0右边为1
这样的区间异或上一个数后，仍然是一个连续的区间
vector<pii> sol;//存储异或以后区间的左右端点
void putin(int l,int r,int b,int e)//存储该区间异或之后的左右端点
{
    int prel=l&(((1<<30)-1)^((1<<b)-1));
    int prer=r&(((1<<30)-1)^((1<<b)-1));
    int pree=e&(((1<<30)-1)^((1<<b)-1));
    sol.push_back(prel^pree,(prel^prer)+(1<<b)-1);//左端点低位的b位为全0，右端点低位b位全1
}

void work(int l,int r,int b,int x,int y,int e)//b为该层线段树区间左右端点低位全0全1的位数
{
    if(x<=l&&r<=y)
    {
        putin(l,r,b,e);
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) work(l,mid,b-1,x,y,e);
    if(y>mid) work(mid+1,r,b-1,x,y,e);
}

void make_condition(int x,int l,int r)//原区间的左右端点l,r，x为区间需要异或的值
{
    work(0,(1<<30)-1,30,l,r,x);
}

特殊的操作
//query函数返回值可以为Node(线段树节点)
//如果查询的值(比如说某种最小值)与涉及到跨区间则写为if(R<=mid) else if(L>mid) else 
//否则可以写为if(L <=mid) if(R > mid) 
int query(int f, int x, int l, int r, int L, int R) {//此处查询满足条件可以到达的最靠左的点
    if (!tr[f][x])return inf;
    if (l == r)return l;
    int mid = l + r >> 1;
    push_down(f, x, l, r, mid);
    if (L <= l && R >= r) {
        if (tr[f][ls] > 0) return query(f, ls, l, mid, l, mid);
        else return query(f, rs, mid + 1, r, mid + 1, r);
    }
    else {
        if (R <= mid)return query(f, ls, l, mid, L, R);//查询区间完全在当前线段树区间左侧，直接返回左边
        else if (L > mid)return query(f, rs, mid + 1, r, L, R);
        else return min(query(f, ls, l, mid, L, mid), query(f, rs, mid + 1, r, mid + 1, R));
        //查询区间在当前线段树区间左右两侧均有
    }
}


#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=200010;
struct point{
    int l,r;
    int v;//区间[l,r]的最大值
}tr[N*4];
int m,p;
void pushup(int u){//由子节点更新父节点
	tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

int query(int u,int l,int r){
    int v=0;
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].v;//如果当前的树已经被包含再查询区间内了，直接放回v
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)v=max(v,query(u<<1,l,r));//否则分别考虑再左节点和右节点是否有查询区间
    if(r>mid)v=max(v,query(u<<1|1,l,r));//区间都是左开右闭的
    return v;
}
void build(int u,int l,int r){//建树，当前节点u，左右端点为l，r
    tr[u]={l,r};
    if(l==r)return;//为叶节点
    int mid=l+r >> 1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int x,int v){//x为需要添加的位置，v为添加的值
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;//如果已经找到了要添加的位置，就直接赋值
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);//递归查询左右区间找位置
        pushup（u）；//等价于tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);更新父节点
    }

}
int main(){
    cin >> m >> p;
    int n=0;//n表示当前树的长度
    int last=0;//last记录一下上一次查询的结果
    
    build(1,1,m);//1表示根节点,m意义为tr[1]的右端点，根据实际情况替换
    while(m--){
        char c;
        int x;
        cin >> c >> x;
        if(c=='Q'){
            last=query(1,n-x+1,n);
            cout << last  << "\n";
        }else{
            modify(1,n+1,(last + x) % p);
            n++;
        }
    }
}

涉及懒标记
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N=100010;

int n,m;
int w[N];
struct Node
{
    int l,r;
    LL sum,add;
}tr[N*4];

void pushup(int u){
    tr[u].sum=tr[u<<1].sum+tr[u<<1 | 1].sum;
}

void pushdown(int u){
    auto &root =tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.add){
        left.add+=root.add,left.sum+=(LL)(left.r-left.l+1)*root.add;
        right.add+=root.add,right.sum+=(LL)(right.r-right.l+1)*root.add;
        root.add=0;
    }
}

void build(int u,int l,int r){
    if(l==r) tr[u]={l,r,w[r],0};
    else{
        tr[u]={l,r};//不要忘了
        int mid=l+r >> 1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

//此时l==r时即为单点修改
//涉及懒标记的更新操作也是关于区间的操作，变为查询操作的形式
void modify(int u,int l,int r,int d){
    if(tr[u].l>=l && tr[u].r<=r){//此时的区间是懒标记已经下传了的
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].add+=d;
    }
    else{ //一定要分裂（pushdown）
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l <= mid) modify(u <<1,l,r,d);//查询区间在当前线段树区间左侧
        if(r > mid) modify(u<<1|1,l,r,d);//查询区间在当前线段树区间右侧
        pushup(u);
    }
}

LL query(int u,int l,int r){
    if(tr[u].l >= l &&tr[u].r <=r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r>>1;
    LL sum=0;
    if(l <=mid) sum=query(u<<1, l,r);//注意是l,r
    if(r > mid) sum+=query(u<<1|1,l,r);
    return sum;
}

int main()
{
    cin >>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    build(1,1,n);
}
多种懒标记，区间加和区间乘
向下传递lazytag的时候人为地为这两个lazytag规定一个先后顺序
先加后乘 :
(a+b)×c=a×c+b×c
先乘后加：
a×c+b
比较一下，发现，上面的先加后乘相当于下面的式子，在加法上面多乘了一个 c
所以，我们只要是先加后乘的式子，只要在 b 上 ×c 就可以转化为先乘后加的式子
具体的操作就是在添加乘法标记的时候，先把加法标记×c就好了
所以，我们就可以给懒标记定义一个固定的顺序：先乘后加
void pushdown(LL o,LL L,LL R) {  //划重点 
    sumv[ls] = mul(sumv[ls],mulv[o]);
    sumv[ls] = add(sumv[ls],addv[o]*(M-L+1)); 
    mulv[ls] = mul(mulv[ls],mulv[o]);
    addv[ls] = mul(addv[ls],mulv[o]);
    addv[ls] = add(addv[ls],addv[o]);
    
    sumv[rs] = mul(sumv[rs],mulv[o]);
    sumv[rs] = add(sumv[rs],addv[o]*(R-M));
    mulv[rs] = mul(mulv[rs],mulv[o]);
    addv[rs] = mul(addv[rs],mulv[o]);
    addv[rs] = add(addv[rs],addv[o]);

    addv[o] = 0;
    mulv[o] = 1;     
}

#include <bits/stdc++.h>
using namespace std;

const int N=200010;

#define lson (id<<1)
#define rson ((id<<1)|1)
#define mid ((l+r)>>1)
#define ls (id<<1)
#define rs (id<<1|1)
struct Node
{
    int val,add,mul;//懒标记，先乘一个数再加一个数
    //这个例子维护的是区间最小值
}tr[N<<2];

void push_up(int id,int l,int r)
{
    tr[id].val=min(tr[lson].val,tr[rson].val);
}

void push_down(int id,int l,int r)
{
    tr[lson].val=tr[lson].val*tr[id].mul+tr[id].add;
    tr[rson].val=tr[rson].val*tr[id].mul+tr[id].add;
    tr[lson].add=tr[lson].add*tr[id].mul+tr[id].add;
    tr[rson].add=tr[rson].add*tr[id].mul+tr[id].add;
    tr[lson].mul=tr[lson].mul*tr[id].mul;
    tr[rson].mul=tr[rson].mul*tr[id].mul;
    tr[id].add=0;
    tr[id].mul=1;
}

void build(int id,int l,int r)
{
    tr[id].mul=1;
    tr[id].add=0;
    if (l==r)
    {
        tr[id].val=0;
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    push_up(id,l,r);
}

void update(int id,int l,int r,int L,int R,int mul,int add)
{
    if (l<r) push_down(id,l,r);
    if (L<=l && R>=r)
    {
        tr[id].add=tr[id].add*mul+add;
        tr[id].mul=tr[id].mul*mul;
        tr[id].val=tr[id].val*mul+add;
        return;
    }

    if(L<=mid) update(lson,l,mid,L,R,mul,add);
    if(R>mid) update(rson,mid+1,r,L,R,mul,add);

    push_up(id,l,r);
}

int query(int id,int l,int r,int L,int R)
{
    if (l<r) push_down(id,l,r);
    if (L<=l && R>=r) return tr[id].val;
    if (mid>=R) return query(lson,l,mid,L,R);
    if (mid<L) return query(rson,mid+1,r,L,R);
    return min(query(lson,l,mid,L,mid),query(rson,mid+1,r,mid+1,R));
}

int n,d;

int main()
{
    build(1,1,d);

    update(1,1,d,l,r,1,1);

    update(1,1,d,l,r,1,-1);
        
    query(1,1,d,1,d);

}


二维线段树
#include <bits/stdc++.h>

using namespace std;

#define son1 o<<2
#define son2 o<<2|1
#define son3 o<<2|2
#define son4 o<<2|3
#define midx (l+r>>1)//注意括号会有优先级的问题
#define midy (u+d>>1)

int n,m,q,a[1005][1005];
struct segtree
{
    int sum,mx;//区间和以及区间最大值
    int laz;
}dat[(1005<<2)*(1005<<2)];

void update(int o)
{
    dat[o].sum=dat[son1].sum+dat[son2].sum+dat[son3].sum+dat[son4].sum;
    dat[o].mx=max((max(dat[son1].sum,dat[son2].sum),dat[son3].sum),dat[son4].sum);
}

//线段树合并，从update函数改
segtree merge(segtree sona,segtree sonb,segtree sonc,segtree sond)
{
    segtree res;
    res.sum=sona.sum+sonb.sum+sonc.sum+sond.sum;
    res.mx=max((max(sona.sum,sonb.sum),sonc.sum),sond.sum);
    return res;
}

void build(int o,int l,int r,int u,int d)
{
    if(l==r && u==d)
    {
        dat[o].sum=dat[o].mx=a[l][u];
        return;
    }
    build(son1,midx+1,r,u,midy);
    build(son2,l,midx,u,midy);
    build(son3,midx+1,r,midy+1,d);
    build(son4,l,midx,midy+1,d);
    update(o);
}

void pushdown(int o,int l,int r,int u,int d)
{
    if(dat[o].laz)
    {
        dat[son1].sum=dat[o].laz*(r-midx)*(midy-u+1);
        dat[son2].sum=dat[o].laz*(midx-l+1)*(midy-u+1);
        dat[son3].sum=dat[o].laz*(r-midx)*(d-midy);
        dat[son4].sum=dat[o].laz*(midx-l+1)*(d-midy);
        dat[son1].mx=dat[son2].mx=dat[son3].mx=dat[son4].mx=dat[o].laz;
        dat[son1].laz=dat[son2].laz=dat[son3].laz=dat[son4].laz=dat[o].laz;
    }
    dat[o].laz=1;
}

void modify(int o,int l,int r,int u,int d,int ql,int qr,int qu,int qd,int v)
{
    if(l>=ql&&r<=qr&&u>=qu&&d<=qd)
    {
        dat[o].sum=v*(r-l+1)*(d-u+1);
        dat[o].mx=v;
        dat[o].laz=v;
        return ;
    }
    pushdown(o,l,r,u,d);
    if(qr>midx&&qu<=midy)
        modify(son1,midx+1,r,u,midy,ql,qr,qu,qd,v);
    if(ql<=midx&&qu<=midy)
        modify(son2,l,midx,u,midy,ql,qr,qu,qd,v);
    if(qr>midx&&qd>midy)
        modify(son3,midx+1,r,midy+1,d,ql,qr,qu,qd,v);
    if(ql<=midx&&qd>midy)
        modify(son4,l,midx,midy+1,d,ql,qr,qu,qd,v);
    update(o);
}

segtree query(int o,int l,int r,int u,int d,int ql,int qr,int qu,int qd)
{
    if(l>=ql&&r<=qr&&u>=qu&&d<=qd)
        return dat[o];
    pushdown(o,l,r,u,d);
    segtree res,sona,sonb,sonc,sond;
    if(qr>midx&&qu<=midy)
        sona=query(son1,midx+1,r,u,midy,ql,qr,qu,qd);
    if(ql<=midx&&qu<=midy)
        sonb=query(son2,l,midx,u,midy,ql,qr,qu,qd);
    if(qr>midx&&qd>midy)
        sonc=query(son3,midx+1,r,midy+1,d,ql,qr,qu,qd);
    if(ql<=midx&&qd>midy)
        sond=query(son4,l,midx,midy+1,d,ql,qr,qu,qd);
    return merge(sona,sonb,sonc,sond);
}

int main()
{
    cin >>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin >>a[i][j];

    build(1,1,n,1,m);
    while(q--)
    {
        int oper;
        cin >>oper;
        if(oper==1)
        {
            int l,r,u,d,v;
            cin >>l>>r>>u>>d>>v;//分别为x,y轴坐标
            modify(1,1,n,1,m,l,r,u,d,v);
        }else if(oper==2)
        {
            int l,r,u,d;
            cin >>l>>r>>u>>d;
            segtree res=query(1,1,n,1,m,l,r,u,d);
            cout <<res.sum<<" "<<res.mx<<endl;
        }
    }
    return 0;
}

权值线段树
/*
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1插入 xx 数
2删除 xx 数(若有多个相同的数，因只删除一个)
3查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
4查询排名为 xx 的数
5求 xx 的前驱(前驱定义为小于 xx，且最大的数)
6求 xx 的后继(后继定义为大于 xx，且最小的数)
*/
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}
const int maxn=111111;
struct seg{
    int v; 
}t[maxn<<3];
void pushup(int o){
    t[o].v=t[o<<1].v+t[o<<1|1].v;
}
void change(int o,int l,int r,int q,int v){
    if(l==r){
        t[o].v+=v;
        return ;
    }
    int mid=l+r>>1;
    if(q<=mid) change(o<<1,l,mid,q,v);
    else change(o<<1|1,mid+1,r,q,v);
    pushup(o);
}
int query_rnk(int o,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr){
        return t[o].v;
    }
    int mid=l+r>>1,ans=0;
    if(ql<=mid) ans+=query_rnk(o<<1,l,mid,ql,qr);
    if(qr>mid) ans+=query_rnk(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
int query_num(int o,int l,int r,int q){
    if(l==r){
        return l;
    }
    int mid=l+r>>1;
    if(t[o<<1].v>=q) return query_num(o<<1,l,mid,q);
    else return query_num(o<<1|1,mid+1,r,q-t[o<<1].v);
}
int lsh[maxn<<2],tot,n;
struct _node{
    int opt,val;
}node[maxn<<2];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        node[i].opt=read();
        node[i].val=read();
        if(node[i].opt==4) continue;
        lsh[++tot]=node[i].val;
    }
    sort(lsh+1,lsh+tot+1);
    tot=unique(lsh+1,lsh+1+tot)-lsh-1;
    for(int i=1;i<=n;i++){
        if(node[i].opt!=4) node[i].val=lower_bound(lsh+1,lsh+tot+1,node[i].val)-lsh;
        if(node[i].opt==1) change(1,1,tot,node[i].val,1);
        if(node[i].opt==2) change(1,1,tot,node[i].val,-1);
        if(node[i].opt==3){
            if(node[i].val==1){
                puts("1");
                continue;
            }
            printf("%d\n",query_rnk(1,1,tot,1,node[i].val-1)+1);
        }
        if(node[i].opt==4){
            printf("%d\n",lsh[query_num(1,1,tot,node[i].val)]);
        }
        if(node[i].opt==5){
            int rk=query_rnk(1,1,tot,1,node[i].val-1);
            printf("%d\n",lsh[query_num(1,1,tot,rk)]);
        }
        if(node[i].opt==6){
            int rk=query_rnk(1,1,tot,1,node[i].val)+1;
            printf("%d\n",lsh[query_num(1,1,tot,rk)]);
        }
    }
    return 0;
}

比起普通线段树，动态开点线段树有一个优势：它能够处理零或负数位置。
此时，求mid时不能用(cl+cr)/2，而要用(cl+cr-1)/2（因为cl等于cr时会退出递归，所以是正确的
动态开点线段树
// MAXV一般能开多大开多大，例如内存限制128M时可以开到八百万左右
namespace SegTree
{
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
#define mark(x) tree[x].mark
using T = int;
const int MAXV = 1.6e7, L = 1, R = 1e9;
const T NA = -2e9;
int cnt = 1;
struct node
{
    T val, mark = NA;
    int ls, rs;
} tree[MAXV];
T op(T a, T b)
{
    return a + b;
}
void upd(int p, T d, int len)
{
    val(p) += d * len;
    mark(p) += d;
}
void push_down(int p, int len)
{
    if (!ls(p)) ls(p) = ++cnt; // 左儿子不存在，创建新节点
    if (!rs(p)) rs(p) = ++cnt; // 右儿子不存在，创建新节点
    if (mark(p) != NA)
    {
        upd(ls(p), mark(p), len / 2);
        upd(rs(p), mark(p), len - len / 2);
        mark(p) = NA;
    }
}
void update(int l, int r, T d, int p = 1, int cl = L, int cr = R)
{
    if (cl >= l && cr <= r)
        return upd(p, d, cr - cl + 1);
    push_down(p, cr - cl + 1);
    int mid = (cl + cr - 1) / 2;
    if (mid >= l)
        update(l, r, d, ls(p), cl, mid);
    if (mid < r)
        update(l, r, d, rs(p), mid + 1, cr);
    val(p) = op(val(ls(p)), val(rs(p)));
}
T query(int l, int r, int p = 1, int cl = L, int cr = R)
{
    if (cl >= l && cr <= r)
        return val(p);
    push_down(p, cr - cl + 1);
    int mid = (cl + cr - 1) / 2;
    if (mid >= r)
        return query(l, r, ls(p), cl, mid);
    else if (mid < l)
        return query(l, r, rs(p), mid + 1, cr);
    else
        return op(query(l, r, ls(p), cl, mid), query(l, r, rs(p), mid + 1, cr));
}
#undef ls
#undef rs
#undef val
#undef mark
}; // namespace SegTree


动态开点权值线段树
// MAXV一般能开多大开多大，例如内存限制128M时可以开到八百万左右
namespace SegTree
{
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
using T = int;
const int MAXV = 8e6, L = -1e7, R = 1e7; // 值域为[L, R]
const T NA = -2e9;
int cnt = 1;
struct node
{
    T val;
    int ls, rs;
} tree[MAXV];
T op(T a, T b)
{
    return a + b;
}
void upd(int p, T d, int len)
{
    val(p) += d * len;
}
void push_down(int p)
{
    if (!ls(p)) ls(p) = ++cnt;
    if (!rs(p)) rs(p) = ++cnt;
}
void update(int x, T d, int p = 1, int cl = L, int cr = R) // 单点修改
{
    if (cl == cr)
        return upd(p, d, 1);
    push_down(p);
    int mid = (cl + cr - 1) / 2;
    if (x <= mid)
        update(x, d, ls(p), cl, mid);
    else
        update(x, d, rs(p), mid + 1, cr);
    val(p) = op(val(ls(p)), val(rs(p)));
}
T query(int l, int r, int p = 1, int cl = L, int cr = R)
{
    if (cl >= l && cr <= r)
        return val(p);
    push_down(p);
    int mid = (cl + cr - 1) / 2;
    if (mid >= r)
        return query(l, r, ls(p), cl, mid);
    else if (mid < l)
        return query(l, r, rs(p), mid + 1, cr);
    else
        return op(query(l, r, ls(p), cl, mid), query(l, r, rs(p), mid + 1, cr));
}
void insert(int v) // 插入
{
    update(v, 1);
}
void remove(int v) // 删除
{
    update(v, -1);
}
int countl(int v)
{
    return query(L, v - 1);
}
int countg(int v)
{
    return query(v + 1, R);
}
int rank(int v) // 求排名
{
    return countl(v) + 1;
}
int kth(int k, int p = 1, int cl = L, int cr = R) // 求指定排名的数
{
    if (cl == cr)
        return cl;
    int mid = (cl + cr - 1) / 2;
    if (val(ls(p)) >= k)
        return kth(k, ls(p), cl, mid); // 往左搜
    else
        return kth(k - val(ls(p)), rs(p), mid + 1, cr); // 往右搜
}
int pre(int v) // 求前驱
{
    int r = countl(v);
    return kth(r);
}
int suc(int v) // 求后继
{
    int r = val(1) - countg(v) + 1;
    return kth(r);
}
#undef ls
#undef rs
#undef val
#undef mark
}; // namespace SegTree


【模板】线段树分裂
因为分裂操作产生新的线段树，所以需要同主席树一样的root数组
集合操作->区间操作->线段树分裂与合并，权值线段树的动态开点
/*
给出一个可重集 aa（编号为 11），它支持以下操作：
0 p x y：将可重集 pp 中大于等于 xx 且小于等于 yy 的值放入一个新的可重集中（新可重集编号为从 22 开始的正整数，是上一次产生的新可重集的编号+1）。
1 p t：将可重集 tt 中的数放入可重集 pp，且清空可重集 tt（数据保证在此后的操作中不会出现可重集 tt）。
2 p x q：在 pp 这个可重集中加入 xx 个数字 qq。
3 p x y：查询可重集 pp 中大于等于 xx 且小于等于 yy 的值的个数。
4 p k：查询在 pp 这个可重集中第 kk 小的数，不存在时输出 -1。
*/
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
//==========================================
const int maxn = 2e5 + 5;
typedef long long ll;
struct Node
{
    int l,r;
    ll val;
}sgt[maxn*40];      //? 40 = 2*maxm*log2(maxn)
int cnt,root[maxn];
inline void pushup(int k) { sgt[k].val = sgt[sgt[k].l].val + sgt[sgt[k].r].val; }
void modify(int l,int r,int &k,int p,int x)     // 单点修改:p位置的值加上x，空间复杂度O(logn)
{
    if(!k) k=++cnt;     // 如果到了NIL结点就新建一个
    sgt[k].val += x;    // 单点修改的加法直接一条线上全部加上x即可
    if(l==r) return;
    int m = (l+r)>>1;
    if(p<=m) modify(l, m, sgt[k].l, p, x);      // 在左子树
    else modify(m+1, r, sgt[k].r, p, x);        // 在右子树
}
//此写法合并操作会对y树造成影响
void merge(int &x,int y)        // 把y结点的内容合并到x结点上，此写法不消耗空间
{
    if(!(x&&y)) x|=y;           // 如果二者有NULL结点
    else 
    {
        sgt[x].val += sgt[y].val;   // 维护加法，直接加就是了
        merge(sgt[x].l, sgt[y].l);  // 递归合并两结点的左子树
        merge(sgt[x].r, sgt[y].r);  // 递归合并两结点的右子树
    }
}
int split(int l,int r,int &k,int x,int y)   // 从编号为k的区间中分离出[x,y]区间并返回新结点编号，空间复杂度O(2logn)
{
    int n = ++cnt;
    if(x<=l&&y>=r)      // 如果k结点维护的区间在[x,y]中
    {
        sgt[n] = sgt[k];    // 直接拿过来便是
        k = 0;              // 置为NULL，断掉联系
    }
    else 
    {
        int m = (l+r)>>1;
        if(x<=m) sgt[n].l = split(l, m, sgt[k].l, x, y);        // 若左子树中有区间信息
        if(y>m)  sgt[n].r = split(m+1, r, sgt[k].r, x, y);      // 若右子树中有区间信息
        pushup(k);
        pushup(n);      // 更改后记得更新值
    }
    return n;
}
ll query(int l,int r,int k,int x,int y)     // 区间查询
{
    if(x<=l&&y>=r) return sgt[k].val;
    int m = (l+r)>>1;
    ll sum = 0;
    if(x<=m) sum += query(l,m,sgt[k].l,x,y);
    if(y>m)  sum += query(m+1,r,sgt[k].r,x,y);
    return sum;
}
ll query(int l,int r,int k,int kth)         // 单点查询
{
    if(l==r) return l;
    int m = (l+r)>>1;
    if(kth<=sgt[sgt[k].l].val) return query(l,m,sgt[k].l,kth);
    else return query(m+1,r,sgt[k].r,kth-sgt[sgt[k].l].val);
}
signed main(signed argc, char const *argv[])
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //======================================
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        modify(1,n,root[1],i,x);            // 初始状态下值都为0，所以加x即为置为x
    }
    int last = 1;
    while(m--)
    {
        int opt,x,y,z;
        cin>>opt>>x>>y;
        switch(opt)
        {
        case 0:
            cin>>z;
            root[++last] = split(1, n, root[x], y, z);
            break;
        case 1:
            merge(root[x],root[y]);
            break;
        case 2:
            cin>>z;
            modify(1,n,root[x],z,y);
            break;
        case 3:
            cin>>z;
            cout<<query(1,n,root[x],y,z)<<endl;
            break;
        case 4:
            if(y>sgt[root[x]].val) cout<<-1<<endl;      // 若只有4个元素却来查询第5大元素（例如），那么结果即为-1
            else cout<<query(1,n,root[x],y)<<endl;
            break;
        }
    }
    //======================================
end:
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;
}

树上差分+线段树合并
/*
首先村落里的一共有 nn 座房屋，并形成一个树状结构。然后救济粮分 mm 次发放，每次选择两个房屋 (x,~y)(x, y)
然后对于 xx 到 yy 的路径上(含 xx 和 yy)每座房子里发放一袋 zz 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
*/
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
//==========================================
#include <cmath>
const int maxn = 1e5 + 5;
typedef pair<int, int> pii;     // first元素存放救济粮数量，second存放该救济粮类型号
struct Node
{
    int l,r;
    pii val;
}sgt[70*maxn];                  //? 70 = 4*maxm*log2(maxn)
int cnt, root[maxn];
pii& max(pii& x, pii& y)        // 因为要取类型号较小的所以无法直接使用max比较
{
    if(x.first>y.first) return x;
    else if(x.first==y.first) return x.second<y.second?x:y;   // 若数量相等取类型号比较小的
    else return y;
}
inline void pushup(int k) { sgt[k].val=max(sgt[sgt[k].l].val, sgt[sgt[k].r].val); }
// 以下为链式前向星
struct E { int v,next; } Edge[maxn<<1];
int tot,Head[maxn];
inline void AddEdge(int u,int v)
{
    Edge[tot]=(E){v,Head[u]};
    Head[u]=tot++;
}
// 以下为树剖求LCA
int dep[maxn], fa[maxn], siz[maxn], son[maxn];
void dfs1(int u,int f)
{
    fa[u]=f, siz[u]=1, dep[u]=dep[f]+1;
    int maxsize = -1;
    for(int i=Head[u];~i;i=Edge[i].next)
    {
        int v = Edge[i].v;
        if(v==f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v]>maxsize)
        {
            son[u]=v;
            maxsize = siz[v];
        }
    }
}
int top[maxn];
void dfs2(int u,int t)
{
    top[u]=t;
    if(son[u]) dfs2(son[u], t);
    for(int i=Head[u];~i;i=Edge[i].next)
    {
        int v = Edge[i].v;
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v, v);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x = fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void modify(int l,int r,int &k,int p,int x)     // 单点修改，空间复杂度O(logn)
{
    if(!k) k=++cnt;
    if(l==r) 
    {
        sgt[k].val.first += x;      // 到叶子结点时使数量加x
        sgt[k].val.second = p;      // 同时捆绑保存住救济粮类型号
        return;
    }
    int m = (l+r)>>1;
    if(p<=m) modify(l, m, sgt[k].l, p, x);
    else modify(m+1, r, sgt[k].r, p, x);
    pushup(k);
}
void merge(int &x,int y,int l=1,int r=maxn)     // 此处的maxn其实是maxk，l与r用于方便判断是否到了叶子结点
{
    if(!(x&&y))
        x|=y;
    else if(l==r) 
        sgt[x].val.first += sgt[y].val.first;   // 到叶子结点时处理有可能发生的同类型救济粮之间的数量叠加
    else
    {
        int m = (l+r)>>1;
        merge(sgt[x].l, sgt[y].l, l, m);
        merge(sgt[x].r, sgt[y].r, m+1, r);
        pushup(x);
    }
}
int ans[maxn];
void dfs(int u)     // dfs处理树上差分
{
    for(int i=Head[u];~i;i=Edge[i].next)
    {
        int v = Edge[i].v;
        if(v==fa[u]) continue;
        dfs(v);     // 头递归
        merge(root[u], root[v]);    // 合并上所有的儿子结点
    }
    if(sgt[root[u]].val.first)      // 若数量不为0，那么second即为u结点数量最多的救济粮
        ans[u]=sgt[root[u]].val.second;
}
#include <cstring>
signed main(signed argc, char const *argv[])
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //======================================
    memset(Head, -1, sizeof(Head));
    int n,m;
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs1(1, 0);
    dfs2(1, 0);
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        // 以下为树上差分基操
        modify(1, maxn, root[x], z, 1);     // x结点加上z救济粮标记
        modify(1, maxn, root[y], z, 1);     // y结点加上z救济粮标记
        modify(1, maxn, root[lca(x,y)], z, -1);     // lca(x,y)结点加上-z救济粮标记
        modify(1, maxn, root[fa[lca(x,y)]], z, -1); // fa[lca(x,y)]结点加上-z救济粮标记
    }
    dfs(1);     // 差分统计
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    //======================================
end:
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;
}


扫描线
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];
struct Node
{
    int l, r;
    int cnt;//被覆盖的次数
    double len;//覆盖的总长度
}tr[N * 8];//*2*4(区间有两个端点)

vector<double> ys;

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];//该区间节点cnt不为0，则len值为区间长度，“+1”是因为区间右端点转换为点坐标
    else if (tr[u].l != tr[u].r)//该区间节点cnt为0而且不是叶节点，len值为两子节点len值之和
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0;//如果为叶节点并且覆盖次数为0
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        pushup(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            seg[j ++ ] = {x1, y1, y2, 1};
            seg[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2);//离散化
        }

        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2);//区间的个数比点的个数少1

        sort(seg, seg + n * 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )
        {
            if (i > 0) res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }

        printf("Test case #%d\n", T ++ );
        printf("Total explored area: %.2lf\n\n", res);
    }

    return 0;
}


主席树//注意多样例时清空t[],root[]

//ps:对于树形结构建立主席树而言，需要dfs来以某节点为上一个版本，子节点为新版本，通俗地说是从根节点到第u号节点的前缀主席树
//还可以对于dfs序建立主席树，这样就便于解决子树问题
/*
for(int i=1;i<=n;i++)
    build(root[i],root[i-1],1,1e9,t[dfn[i]]);
*/
dfs(1,0);
void dfs(int u,int fa)
{
    root[u]=insert(root[fa],0,nums.size()-1,find(w[u]));
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u);
    }
}
//ps

int cnt,root[100005];
struct hjtree
{
    int l,r;
    int v;//区间中权值个数
}t[100005<<6];

//主席树只支持单点修改，每次插入一个值
//此处的&o对应的会将新点的cnt赋给root[i]
void build(int &o,int pre,int l,int r,int x)//o为当前结点，pre为前驱结点，l-r为当前区间
{
    o=++cnt;
    t[o]=t[pre];//当前节点要在前驱的基础上修改，才能保证只增加logn个节点
    t[o].v++;
    if(l==r)//修改到叶子节点就返回
    {
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid)
        build(t[o].l,t[pre].l,l,mid,x,v);
    else 
        build(t[o].r,t[pre].r,mid+1,r,x,v);
}

int query(int ox,int oy,int l,int r,int ql,int qr)//ox为树r节点，oy为树l-1节点，l-r为当前区间，ql-qr为所求区间
{
    if(l>=ql&&r<=qr)
        return t[ox].v-t[oy].v;//返回前缀和
    int res=0;
    int mid=l+r>>1;
    if(ql<=mid)
        res+=query(t[ox].l,t[oy].l,l,mid,ql,qr);
    if(qr>mid)
        res+=query(t[ox].r,t[oy].r,mid+1,r,ql,qr);
    return res;
}

例题
/*
给一个长度为 n 的正整数序列 a。共有 m 组询问，每次询问一个区间[l,r]
是否存在一个数在 [l,r] 中出现的次数严格大于一半。
如果存在，输出这个数，否则输出 0。
*/
#include <bits/stdc++.h>
#define int long long
#define mid (l+r)/2
using namespace std;

int n,q;
int cnt,root[500005];
struct hjtree
{
    int l,r;
    int v;
}t[500005<<6];

//主席树只支持单点修改，每次插入一个值
void build(int &o,int pre,int l,int r,int x)//o为当前结点，pre为前驱结点，l-r为当前区间
{
    o=++cnt;
    t[o]=t[pre];//当前节点要在前驱的基础上修改，才能保证只增加logn个节点
    t[o].v++;
    if(l==r)//修改到叶子节点就返回
        return ;
    if(x<=mid)
        build(t[o].l,t[pre].l,l,mid,x);
    else
        build(t[o].r,t[pre].r,mid+1,r,x);
}

int query(int ox,int oy,int l,int r,int k)//ox为树r节点，oy为树l-1节点，l-r为当前区间
{
    if(t[ox].v-t[oy].v<=k)
        return 0;
    if(l==r)//如果查询到了叶子节点说明合法
        return l;
    return max(query(t[ox].l,t[oy].l,l,mid,k),query(t[ox].r,t[oy].r,mid+1,r,k));
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >>n>>q;
    for(int i=1,x;i<=n&&cin >>x;i++)
        build(root[i],root[i-1],1,n,x);//对每个数分别建树
    //当前根节点在上一个根节点上修改，修改位置为x

    while(q--)
    {
        int l,r;
        cin >>l>>r;
        cout <<query(root[r],root[l-1],1,n,(r-l+1)/2)<<endl;
    }

    return 0;
}

静态第K小
/**
* All rights reserved.
* Author : Horizon
* Date : 2021-08-08-21.06.39
* Description : dfs
*/
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,M=1e4+5;
int n,m;//n个数m次询问
int a[N];
vector<int> nums;

struct Node
{
    int l,r;
    int cnt;
}tr[N*4+N*17];//第一个版本占一个线段树的空间N*4,然后后面的版本占logN的空间

int root[N],idx;//n个版本

int find(int x)
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

//因为节点的左右子树以指针相连所以需要给出节点左右边界,即为0-nums.size()-1
int build(int l,int r)
{
    int p=++idx;
    if(l==r) return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

//用p表示上一个版本，q表示新版本
int insert(int p,int l,int r,int x)
{
    int q=++idx;
    tr[q]=tr[p];//先将上一个版本复制过来
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
    else tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;//pushup
    return q;
}

//tr[q].l和tr[q].r即为左右节点的指针
int query(int q,int p,int l,int r,int k)
{
    if(l==r) return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin >>a[i];
        nums.push_back(a[i]);
    }

    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());

    root[0]=build(0,nums.size()-1);

    for(int i=1;i<=n;i++)
        root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));

    while(m--)
    {
        int l,r,k;
        cin >>l>>r>>k;
        cout <<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;//注意是root[r]和root[l-1]，而不是r和l-1
    }

    return 0;
}


静态区间k小个数的和
//易错点：递归到叶子节点时应该返回的值应该是 rank×val(此处rank相当于k) 而不是直接返回一个 val 
long long query(int l,int r,int nl,int nr,int rank)
{
    if(l == r) return rank * cmt[l];
    int mid = (l + r) >> 1 , Sum = tree[tree[nr].l].sum - tree[tree[nl].l].sum;long long res = 0;
    if(rank <= Sum) res += query(l , mid , tree[nl].l , tree[nr].l , rank);
    else 
    {
        res += tree[tree[nr].l].fsum - tree[tree[nl].l].fsum;
        res += query(mid + 1 , r , tree[nl].r , tree[nr].r , rank - Sum);   
    } 
    return res;
}


动态区间第k小
主席树+树状数组思路优化
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=10005;
struct segment_tree{int v;int ls,rs;}t[MAX*400];//线段树开nlogn大小
struct operation{bool b;int l,r,k;int pos,t;}q[MAX];//因为要离散花所以要把所有数据输进来离线搞
int n,m,a[MAX],o[MAX<<1],rt[MAX],len,tot,temp[2][20],cnt[2];
char opt;
void Modify(int &now,int l,int r,int pos,int val)//此时当前版本和上一个版本无关
{
    if (!now) now=++tot;
    t[now].v+=val;
    if (l==r) return;
    int mid=l+r>>1;
    if (pos<=mid) Modify(t[now].ls,l,mid,pos,val);
    else Modify(t[now].rs,mid+1,r,pos,val);
}
void prepare_Modify(int x,int val)
{
    int k=lower_bound(o+1,o+len+1,a[x])-o;
    for (int i=x;i<=n;i+=i&-i) Modify(rt[i],1,len,k,val);//处理出需要修改哪log棵主席树
}
int Query(int l,int r,int k)
{
    if (l==r) return l;
    int mid=l+r>>1,sum=0;
    for (int i=1;i<=cnt[1];i++) sum+=t[t[temp[1][i]].ls].v;
    for (int i=1;i<=cnt[0];i++) sum-=t[t[temp[0][i]].ls].v;
    if (k<=sum)
    {
        for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].ls;
        for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].ls;
        return Query(l,mid,k);
    }
    else
    {
        for (int i=1;i<=cnt[1];i++) temp[1][i]=t[temp[1][i]].rs;
        for (int i=1;i<=cnt[0];i++) temp[0][i]=t[temp[0][i]].rs;
        return Query(mid+1,r,k-sum);
    }
}
int prepare_Query(int l,int r,int k)
{
    memset(temp,0,sizeof(temp));//同修改，处理出需要进行相减操作的是哪log棵主席树
    cnt[0]=cnt[1]=0;
    for (int i=r;i;i-=i&-i) temp[1][++cnt[1]]=rt[i];
    for (int i=l-1;i;i-=i&-i) temp[0][++cnt[0]]=rt[i];
    return Query(1,len,k);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i],o[++len]=a[i];
    for (int i=1;i<=m;i++)
    {
        cin>>opt;
        q[i].b=(opt=='Q');
        if (q[i].b)    cin>>q[i].l>>q[i].r>>q[i].k;
        else cin>>q[i].pos>>q[i].t,o[++len]=q[i].t;
    }
    sort(o+1,o+len+1);
    len=unique(o+1,o+len+1)-o-1;//离散 —— 排序 + 去重
    for (int i=1;i<=n;i++) prepare_Modify(i,1);
    for (int i=1;i<=m;i++)
    {
        if (q[i].b)    printf("%d\n",o[prepare_Query(q[i].l,q[i].r,q[i].k)]);
        else
        {
            prepare_Modify(q[i].pos,-1);
            a[q[i].pos]=q[i].t;
            prepare_Modify(q[i].pos,1);
        }
    }
    return 0;
}


区间修改的主席树
const int N = 3e5 + 10;

struct node {
    int ls, rs;
    int sum, tag;
}hjt[N*50];
int cnt, rt[N];
void modify(int &now, int pre, int ql, int qr, int l, int r, int val) {
    now = ++cnt;
    hjt[now] = hjt[pre];
    hjt[now].sum += (min(qr, r) - max(ql, l) + 1) * val;
    if (ql <= l && qr >= r) {
        hjt[now].tag += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) modify(hjt[now].ls, hjt[pre].ls, ql, qr, l, mid, val);
    if (qr > mid) modify(hjt[now].rs, hjt[pre].rs, ql, qr, mid+1, r, val);
}
int query(int now, int pre, int ql, int qr, int l, int r) {
    if (ql <= l && qr >= r) return hjt[now].sum - hjt[pre].sum;
    int mid = (l + r) >> 1;
    int ans = (min(qr, r) - max(ql, l) + 1) * (hjt[now].tag - hjt[pre].tag);
    if (ql <= mid) ans += query(hjt[now].ls, hjt[pre].ls, ql, qr, l, mid);
    if (qr > mid) ans += query(hjt[now].rs, hjt[pre].rs, ql, qr, mid+1, r);
    return ans;
}


颜色块均摊+主席树(两棵主席树)//
/*
给一个序列
每个位置有初值ai，最大值mi，这个值每秒会增大ri，直到mi
有m个发生时间依此增大的询问，每次询问区间和并且将区间的所有数字变成0
*/
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T>
inline bool chkmax(T &i,const T&j){return i<j?(i=j,1):0;}
template<typename T>
inline bool chkmin(T &i,const T&j){return i>j?(i=j,1):0;}
template<typename T> void Read(T &x){
    x=0;int f=1;
    char ch=getchar();
    while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    x=x*f;
}

typedef long long ll;
#define INF 0x3f3f3f3f
const int N=1e5+5,SIZ=1e7+5,V=1e5+5;
int n,s[N],mx[N],r[N];
#define ls(xx) t[xx].ls
#define rs(xx) t[xx].rs
int tot=0,root[N],root1[N];
struct Node{
    int l,r,ls,rs;ll v;
}t[SIZ];
void Pushup(int p){t[p].v=t[ls(p)].v+t[rs(p)].v;}
void Build(int p,int l,int r){//建立一棵空的主席树
    t[p].l=l,t[p].r=r;
    if(t[p].l==t[p].r) return;
    int mid=(l+r)>>1;
    Build(ls(p)=++tot,l,mid);Build(rs(p)=++tot,mid+1,r);
}
int Add(int p,int x,ll k){//在上一个版本的基础上进行单点修改
    int np=++tot;t[np]=t[p];
    if(t[np].l==t[np].r){
        t[np].v+=k;return np;
    }int mid=(t[np].l+t[np].r)>>1;
    if(x<=mid) ls(np)=Add(ls(p),x,k);
    else rs(np)=Add(rs(p),x,k);
    Pushup(np);return np;
}
ll QLe(int p,int x){//查找主席树中≤x的和
    if(t[p].r<=x) return t[p].v;
    int mid=(t[p].l+t[p].r)>>1;ll res=0;
    if(ls(p)) res+=QLe(ls(p),x);
    if(x>mid) res+=QLe(rs(p),x);
    return res;
}
ll QGe(int p,int x){//查找主席树中≥x的和
    if(t[p].l>=x) return t[p].v;
    int mid=(t[p].l+t[p].r)>>1;ll res=0;
    if(x<=mid) res+=QGe(ls(p),x);
    if(rs(p)) res+=QGe(rs(p),x);
    return res;
}
struct Seg{//orig用来存区间是否有初值（是否被区间赋值过），lst记录区间上次被修改的时间
    int l,r,orig,lst;
};
bool operator<(const Seg &x,const Seg &y){
    return x.l<y.l;
}
typedef set<Seg>::iterator Iter;
set<Seg> st;
ll Bf(const Seg &it,int t){//暴力
    ll res=0;
    For(i,it.l,it.r){
        res+=min(1LL*mx[i],s[i]+1LL*(t-it.lst)*r[i]);
        s[i]=0;
    }return res;
}
ll Qry(const Seg &it,int t){
    if(it.orig) return Bf(it,t);
    t-=it.lst;
    return 1LL*t*(QGe(root1[it.r],t)-QGe(root1[it.l-1],t))+QLe(root[it.r],t-1)-QLe(root[it.l-1],t-1);
}
int m;
int main(){

#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif // LOCAL

    Read(n);
    root[0]=tot=1;t[tot].l=0,t[tot].r=V;
    Build(root[0],0,V);
    root1[0]=++tot;t[tot].l=0,t[tot].r=V;
    Build(root1[0],0,V);
    For(i,1,n){
        Read(s[i]);Read(mx[i]);Read(r[i]);
        if(r[i]==0){//对于r[i]==0的情况要特判
            root[i]=Add(root[i-1],0,0);
            root1[i]=Add(root1[i-1],0,0);
            continue;
        }
        root[i]=Add(root[i-1],mx[i]/r[i],mx[i]);
        root1[i]=Add(root1[i-1],mx[i]/r[i],r[i]);
    }
    Read(m);
    st.insert(Seg{1,n,1,0});
    int t=0,l,r;
    while(m--){
        Read(t);Read(l);Read(r);
        ll ans=0;
        Iter it1=--st.upper_bound(Seg{l,0,0,0}),it2=--st.upper_bound(Seg{r,0,0,0});
        
        if(it1==it2){//l,r在set内处于同一个区间
            ans+=Qry(Seg{l,r,it1->orig,it1->lst},t);
            Seg is=*it1;
            st.erase(it1);
            if(l!=is.l) st.insert(Seg{is.l,l-1,is.orig,is.lst});
            st.insert(Seg{l,r,0,t});
            if(r!=is.r) st.insert(Seg{r+1,is.r,is.orig,is.lst});
        }else{
            ans+=Qry(Seg{l,it1->r,it1->orig,it1->lst},t);
            Seg is1=*it1,is2=*it2;
            for(Iter it=st.erase(it1);it!=it2&&it!=st.end();it=st.erase(it)){
                ans+=Qry(*it,t);
            }
            ans+=Qry(Seg{it2->l,r,it2->orig,it2->lst},t);
            st.erase(it2);
            if(is1.l<=l-1) st.insert(Seg{is1.l,l-1,is1.orig,is1.lst});
            if(is2.r>=r+1) st.insert(Seg{r+1,is2.r,is2.orig,is2.lst});
            st.insert(Seg{l,r,0,t});
        }
        printf("%lld\n",ans);
    }
    return 0;
}


分块
/*
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
还可以解决给一个数组，初始所有位置全是0，每次单点加一或减一，询问区间有多少个位置不为0。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 100010, M = 350;

int n, m, len;
LL add[M], sum[M];//add为懒标记
int w[N];

int get(int i)//将数组的位置映射到块中
{
    return i / len;
}

void change(int l, int r, int d)
{
    if (get(l) == get(r))  // 段内直接暴力,边界情况
    {
        for (int i = l; i <= r; i ++ ) w[i] += d, sum[get(i)] += d;
    }
    else
    {
        int i = l, j = r;
        //处理不完整段
        while (get(i) == get(l)) w[i] += d, sum[get(i)] += d, i ++ ;
        while (get(j) == get(r)) w[j] += d, sum[get(j)] += d, j -- ;
        //处理完整段
        for (int k = get(i); k <= get(j); k ++ ) sum[k] += len * d, add[k] += d;
    }
}

LL query(int l, int r)
{
    LL res = 0;
    if (get(l) == get(r))  // 段内直接暴力
    {
        for (int i = l; i <= r; i ++ ) res += w[i] + add[get(i)];
    }
    else
    {
        int i = l, j = r;
        while (get(i) == get(l)) res += w[i] + add[get(i)], i ++ ;
        while (get(j) == get(r)) res += w[j] + add[get(j)], j -- ;
        for (int k = get(i); k <= get(j); k ++ ) res += sum[k];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[i]);
        sum[get(i)] += w[i];
    }

    char op[2];
    int l, r, d;
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C')
        {
            scanf("%d", &d);
            change(l, r, d);
        }
        else printf("%lld\n", query(l, r));
    }

    return 0;
}

涉及单点更新以及区间最大值查询
const int maxn=2e5+7;
int block,belong[maxn],num,l[maxn],r[maxn],n,q;
int a[maxn],Max[maxn];

void build()
{
    for(int i=1;i<=n;i++)
        cin >>a[i];
    blocks=sqrt(n);//块内元素个数
    num=n/block;//多少个块
    memset(Max,0,sizeof(int)*(num+4));
    if(n%block) num++;
    for(int i=1;i<=num;i++)//每个块左边元素右边元素的ID是什么
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=num;i++)//每一个i属于哪一个块
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        for(int j=l[i];j<=r[i];j++)
            Max[i]=max(Max[i],a[j]);//根据题面预处理，此处为区间最大值
}

void update(int x,int y)
{
    a[x]=y,Max[belong[x]]=0;
    for(int i=l[belong[x]];i<=r[belong[x]];i++)
        Max[belong[x]]=max(Max[belong[x]],a[i]);
}

int ask(int x,int y)
{
    int ans=0;
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
            ans=max(a[i],ans);//...
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++)
        ans=max(ans,a[i]);
    for(int i=belong[x]+1;i<belong[y];i++)
        ans=max(ans,Max[i]);
    for(int i=l[belong[y]];i<=y;i++)
        ans=max(ans,a[i]);
    return ans;
}

基础莫队
一种套路：可以用莫队查询，对值域分块（hdu多校1，2）
/*
给出一个序列和若干查询l, r，问[l, r]中有多少个不同的数
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 50010, M = 200010, S = 1000010;

int n, m, len;
int w[N], ans[M];
struct Query
{
    int id, l, r;
    bool operator<(const Query &o) const // 重载<运算符，奇偶化排序
    {
        if ( get(l) != get(o.l)) 
            return l < o.l;
        if ( get(l) & 1)
            return r < o.r;
        return r > o.r;
    }
}q[M];
int cnt[S];

int get(int x)
{
    return x / len;
}

void add(int x, int& res)
{
    if (!cnt[x]) res ++ ;
    cnt[x] ++ ;
}

void del(int x, int& res)
{
    cnt[x] -- ;
    if (!cnt[x]) res -- ;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    scanf("%d", &m);
    len = sqrt((double)n * n / m);//块长取n*n/m更好,此时复杂度为O(n*m^(1/2)) (double)在pow函数中也用了

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }
    sort(q, q + m);

    for (int k = 0, i = 0, j = 1, res = 0; k < m; k ++ )//i在后 j在前 初始时表示为空
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) add(w[ ++ i], res);
        while (i > r) del(w[i -- ], res);
        while (j < l) del(w[j ++ ], res);
        while (j > l) add(w[ -- j], res);
        ans[id] = res;
    }

    for (int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);
    return 0;
}


带修改的莫队
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 10010, S = 1000010;

int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct Query
{
    int id, l, r, t;
}q[N];
struct Modify
{
    int p, c;
}c[N];

int get(int x)
{
    return x / len;
}

bool cmp(const Query& a, const Query& b)
{
    int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl) return al < bl;
    if (ar != br) return ar < br;
    return a.t < b.t;
}

void add(int x, int& res)
{
    if (!cnt[x]) res ++ ;
    cnt[x] ++ ;
}

void del(int x, int& res)
{
    cnt[x] -- ;
    if (!cnt[x]) res -- ;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < m; i ++ )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q') mq ++, q[mq] = {mq, a, b, mc};
        else c[ ++ mc] = {a, b};
    }

    len = cbrt((double)n * mc) + 1;
    sort(q + 1, q + mq + 1, cmp);

    for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++ )
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        while (i < r) add(w[ ++ i], res);
        while (i > r) del(w[i -- ], res);
        while (j < l) del(w[j ++ ], res);
        while (j > l) add(w[ -- j], res);
        while (t < tm)
        {
            t ++ ;
            if (c[t].p >= j && c[t].p <= i)//j-i
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
        }
        while (t > tm)
        {
            if (c[t].p >= j && c[t].p <= i)
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
            t -- ;
        }
        ans[id] = res;
    }

    for (int i = 1; i <= mq; i ++ ) printf("%d\n", ans[i]);
    return 0;
}


树上莫队
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int N = 100010;

int n, m, len;
int w[N];
int h[N], e[N], ne[N], idx;
int depth[N], f[N][16];
int seq[N], top, first[N], last[N];//seq欧拉序
int cnt[N], st[N], ans[N];//st记录区间中数出现0/1次
int que[N];
struct Query
{
    int id, l, r, p;
}q[N];
vector<int> nums;

void add_edge(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
    seq[ ++ top] = u;
    first[u] = top;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father) dfs(j, u);
    }
    seq[ ++ top] = u;
    last[u] = top;
}

void bfs()
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    int hh = 0, tt = 0;
    que[0] = 1;
    while (hh <= tt)
    {
        int t = que[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                f[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    f[j][k] = f[f[j][k - 1]][k - 1];
                que[ ++ tt] = j;
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (f[a][k] != f[b][k])
        {
            a = f[a][k];
            b = f[b][k];
        }
    return f[a][0];
}

int get(int x)
{
    return x / len;
}

bool cmp(const Query& a, const Query& b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

void add(int x, int& res)
{
    st[x] ^= 1;
    if (st[x] == 0)
    {
        cnt[w[x]] -- ;
        if (!cnt[w[x]]) res -- ;
    }
    else
    {
        if (!cnt[w[x]]) res ++ ;
        cnt[w[x]] ++ ;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), nums.push_back(w[i]);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n; i ++ )
        w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b), add_edge(b, a);
    }

    dfs(1, -1);
    bfs();

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (first[a] > first[b]) swap(a, b);
        int p = lca(a, b);
        if (a == p) q[i] = {i, first[a], first[b]};//询问的区间
        else q[i] = {i, last[a], first[b], p};//p表示询问区间要加上lca
    }

    len = sqrt(top);
    sort(q, q + m, cmp);

    for (int i = 0, L = 1, R = 0, res = 0; i < m; i ++ )
    {
        int id = q[i].id, l = q[i].l, r = q[i].r, p = q[i].p;
        while (R < r) add(seq[ ++ R], res);
        while (R > r) add(seq[R -- ], res);
        while (L < l) add(seq[L ++ ], res);
        while (L > l) add(seq[ -- L], res);
        if (p) add(p, res);
        ans[id] = res;
        if (p) add(p, res);//减去lca
    }

    for (int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);

    return 0;
}

回滚莫队
/*
日记中记录了连续N天发生的时间，大约每天发生一件。
事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。
JOI教授决定用如下的方法分析这些日记：
1.选择日记中连续的一些天作为分析的时间段
2.事件种类t的重要度为t×(这段时间内重要度为t的事件数)
3.计算出所有事件种类的重要度，输出其中的最大值
现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 100100
#define maxb 5050
#define ll long long
int aa[maxn], typ[maxn], cnt[maxn], cnt2[maxn], belong[maxn], lb[maxn], rb[maxn], inp[maxn];
ll ans[maxn];
struct query {
    int l, r, id;
} q[maxn];
int n, m, size, bnum;
#define isdigit(x) ((x) >= '0' && (x) <= '9')
inline int read() {
    int res = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();
    return res;
}
int cmp(query a, query b) {
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : a.r < b.r; 
}
int main() {
    n = read(), m = read();
    size = sqrt(n);
    bnum = ceil((double) n / size);
    for(int i = 1; i <= bnum; ++i) {
        lb[i] = size * (i - 1) + 1;
        rb[i] = size * i;
        for(int j = lb[i]; j <= rb[i]; ++j) belong[j] = i;
    }
    rb[bnum] = n;
    for(int i = 1; i <= n; ++i) inp[i] = aa[i] = read();
    sort(inp + 1, inp + n + 1);
    int tot = unique(inp + 1, inp + n + 1) - inp - 1;
    for(int i = 1; i <= n; ++i) typ[i] = lower_bound(inp + 1, inp + tot + 1, aa[i]) - inp;
    for(int i = 1; i <= m; ++i) {
        q[i].l = read(), q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int i = 1;
    for(int k = 0; k <= bnum; ++k) {
        int l = rb[k] + 1, r = rb[k];
        ll now = 0;
        memset(cnt, 0, sizeof(cnt));
        for( ; belong[q[i].l] == k; ++i) {
            int ql = q[i].l, qr = q[i].r;
            ll tmp;
            if(belong[ql] == belong[qr]) {
                tmp = 0;
                for(int j = ql; j <= qr; ++j) cnt2[typ[j]] = 0;
                for(int j = ql; j <= qr; ++j) {
                    ++cnt2[typ[j]]; tmp = max(tmp, 1ll * cnt2[typ[j]] * aa[j]);
                }
                ans[q[i].id] = tmp;
                continue;
            }
            while(r < qr) {
                ++r; ++cnt[typ[r]]; now = max(now, 1ll * cnt[typ[r]] * aa[r]);
            }
            tmp = now;
            while(l > ql){
                --l; ++cnt[typ[l]]; now = max(now, 1ll * cnt[typ[l]] * aa[l]);
            } 
            ans[q[i].id] = now;
            while(l < rb[k] + 1) {
                --cnt[typ[l]];
                l++;
            }
            now = tmp;
        }
    }
    for(int i = 1; i <= m; ++i) printf("%lld\n", ans[i]);
    return 0;
}


倍增法求最近公共祖先lca
/*
若已经通过dfs求得了每个节点的父节点fa，那么bfs函数可以被替换为
for (int i=1;i<=n;i++) up[i][0]=fa[i];

for (int j=1;j<=20;j++) {
    for (int i=1;i<=n;i++) {
        up[i][j]=up[up[i][j-1]][j-1];
    }
}
这里的up数组意义就是下面的fa数组
*/

/*
倍增法的其他应用：
假设树中根节点的权值到各叶子节点路径上权值不断递减，求从x节点向上走深度最小的权值<r的节点是哪个
for(int i=20;i>=0;i--)
    if(t[fas[x][i]]<=r) x=fas[x][i];
*/

给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。
有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16];//fa数组的第二维大小需要根据树中节点个数调整
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 15; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

int main()
{
    scanf("%d", &n);
    int root = 0;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }

    bfs(root);

    scanf("%d", &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }

    return 0;
}


树链剖分求lca
int LCA(int x,int y){
    while(top[x]!=top[y])
    dep[top[x]]>=dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]>=dep[y]?y:x;
}


/*
对一棵树进行深度优先搜索时，无论第一次访问还是回溯到某一个节点
都将该编号按顺序记录下来，并打下访问的时间戳，可以得到长度为2*n-1的序列 
*/
欧拉序//子树在dfs序上一定连续
vector<int> G2[N];
int n, in[N], out[N], tot;//in、out分别存储该点入点和出点时间戳
//节点x以及其子树即为in[x]-out[x]，开始到结束

for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G2[u].push_back(v);
    G2[v].push_back(u);
}

void dfs1(int x, int fa) {
    in[x] = ++tot;
    for (auto v : G2[x]) {
        if (v == fa) continue;
        dfs1(v, x);
    }
    out[x] = tot;
}
//dfs1的过程中还可以求出dfs序和父节点
int fa[N],dfn[N];
void dfs1(int x, int fa) {
    fa[x]=fa;
    in[x] = ++tot;
    dfn[tot]=x;
    for (auto v : G2[x]) {
        if (v == fa) continue;
        dfs1(v, x);
    }
    out[x] = tot;
}

树链剖分
/*
给定一棵树，树中包含 n 个节点（编号 1∼n），其中第 i 个节点的权值为 ai。

初始时，1 号节点为树的根节点。

现在要对该树进行 m 次操作，操作分为以下 4 种类型：

1 u v k，修改路径上节点权值，将节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值增加 k。
2 u k，修改子树上节点权值，将以节点 u 为根的子树上的所有节点的权值增加 k。
3 u v，询问路径，询问节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值和。
4 u，询问子树，询问以节点 u 为根的子树上的所有节点的权值和。
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010, M = N * 2;

int n, m;
int w[N], h[N], e[M], ne[M], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct Tree
{
    int l, r;
    LL add, sum;
}tr[N * 4];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u, int father, int depth)//求出各点父节点、深度、重儿子、子树大小
{
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u, depth + 1);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

//当前点的权值存入数组nw中该点时间戳位置，最后按时间戳遍历即为dfs序
void dfs2(int u, int t)//求出各点的时间戳、dfs序、所在重链的“头”
{
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
    if (!son[u]) return;//没有儿子则也没有重儿子
    dfs2(son[u], t);//往重儿子走，其“头”还是t
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;//邻接点为父亲以及重儿子的情况
        dfs2(j, j);
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += root.add * (left.r - left.l + 1);
        right.add += root.add, right.sum += root.add * (right.r - right.l + 1);
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, nw[r]};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int k)
{
    if (l <= tr[u].l && r >= tr[u].r)
    {
        tr[u].add += k;
        tr[u].sum += k * (tr[u].r - tr[u].l + 1);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) update(u << 1, l, r, k);
    if (r > mid) update(u << 1 | 1, l, r, k);
    pushup(u);
}

LL query(int u, int l, int r)
{
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

void update_path(int u, int v, int k)
{
    while (top[u] != top[v])//u、v不在一条重链上
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);//让“头”深度更大的节点向上跳
        update(1, id[top[u]], id[u], k);//修改该点到其“头”的这段，因为连续
        u = fa[top[u]];//将“头”深度更大的父亲重新赋给u，准备下一轮跳
    }
    if (dep[u] < dep[v]) swap(u, v);
    update(1, id[v], id[u], k);//此时u、v在一条重链上
}

LL query_path(int u, int v)
{
    LL res = 0;
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, id[top[u]], id[u]);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) swap(u, v);
    res += query(1, id[v], id[u]);
    return res;
}

void update_tree(int u, int k)
{
    update(1, id[u], id[u] + sz[u] - 1, k);
}

LL query_tree(int u)
{
    return query(1, id[u], id[u] + sz[u] - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs1(1, -1, 1);
    dfs2(1, 1);
    build(1, 1, n);

    scanf("%d", &m);
    while (m -- )
    {
        int t, u, v, k;
        scanf("%d%d", &t, &u);
        if (t == 1)
        {
            scanf("%d%d", &v, &k);
            update_path(u, v, k);
        }
        else if (t == 2)
        {
            scanf("%d", &k);
            update_tree(u, k);
        }
        else if (t == 3)
        {
            scanf("%d", &v);
            printf("%lld\n", query_path(u, v));
        }
        else printf("%lld\n", query_tree(u));
    }

    return 0;
}


杭电2021多校第二场 HDU 6962 I love tree
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n;
vector<int>v[N];
int fa[N],depth[N],se[N],son[N],dfn[N],tot,top[N];

struct Seg {
    struct Node {
        int l,r;
        LL sum,lazy;
    }tr[N<<2];
    
    void pushup(int u) {
        tr[u].sum=tr[L].sum+tr[R].sum;
    }
    
    void pushdown(int u) {
        LL lazy=tr[u].lazy; tr[u].lazy=0;
        tr[L].sum+=lazy*Len(L); tr[L].lazy+=lazy;
        tr[R].sum+=lazy*Len(R); tr[R].lazy+=lazy;
    }
    
    void build(int u,int l,int r) {
        tr[u]={l,r};
        if(l==r) return;
        build(L,l,Mid); build(R,Mid+1,r);
    }
    
    void change(int u,int l,int r,LL sum) {
        if(tr[u].l>=l&&tr[u].r<=r) {
            tr[u].sum+=Len(u)*sum;
            tr[u].lazy+=sum;
            return ;
        }
        pushdown(u);
        if(l<=Mid) change(L,l,r,sum);
        if(r>Mid) change(R,l,r,sum);
        // pushup(u);
    }
    
    LL query(int u,int pos) {
        if(tr[u].l==tr[u].r) return tr[u].sum;
        pushdown(u);
        if(pos<=Mid) return query(L,pos);
        else return query(R,pos);
        // pushup(u);
    }
}t1,t2,t3;

void dfs1(int u,int f) {
    depth[u]=depth[f]+1; fa[u]=f;
    se[u]=1;
    for(auto x:v[u]) {
        if(x==f) continue;
        dfs1(x,u);
        se[u]+=se[x];
        if(se[x]>se[son[u]]) son[u]=x;
    }
}

void dfs2(int u,int t) {
    top[u]=t; dfn[u]=++tot;
    if(son[u]) dfs2(son[u],t);
    for(auto x:v[u]) {
        if(x==son[u]||x==fa[u]) continue;
        dfs2(x,x);
    }
}

void change(int x,int y,int cnt) {
    int l=1,r=cnt;
    while(top[x]!=top[y]) {
        if(depth[top[x]]>depth[top[y]]) {
            LL add=dfn[x]+l; 
            l+=depth[x]-depth[top[x]]+1;
            t1.change(1,dfn[top[x]],dfn[x],1);
            t2.change(1,dfn[top[x]],dfn[x],add*add);
            t3.change(1,dfn[top[x]],dfn[x],add);
            x=fa[top[x]];
        } else {
            int now=depth[y]-depth[top[y]]+1;
            LL add=dfn[top[y]]+(r-now-1); r-=now;
            t1.change(1,dfn[top[y]],dfn[y],1);
            t2.change(1,dfn[top[y]],dfn[y],add*add);
            t3.change(1,dfn[top[y]],dfn[y],add);
            y=fa[top[y]];
        }
    }
    if(depth[x]>depth[y]) {
        LL add=dfn[x]+l; l+=depth[x]-depth[y]+1;
        t1.change(1,dfn[y],dfn[x],1);
        t2.change(1,dfn[y],dfn[x],add*add);
        t3.change(1,dfn[y],dfn[x],add);
    } else {
        int now=depth[y]-depth[x]+1;
        LL add=dfn[x]-(r-now+1); r-=now;
        t1.change(1,dfn[x],dfn[y],1);
        t2.change(1,dfn[x],dfn[y],add*add);
        t3.change(1,dfn[x],dfn[y],add);
    }
}

int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(depth[x]<depth[y]) return x;
    else return y;
}

int main()
{
//  ios::sync_with_stdio(false);
//  cin.tie(0);

    scanf("%d",&n);
    for(int i=1;i<=n-1;i++) {
        int a,b; scanf("%d%d",&a,&b);
        v[a].pb(b); v[b].pb(a);
    }
    dfs1(1,0); dfs2(1,1);
    t1.build(1,1,n); t2.build(1,1,n); t3.build(1,1,n);
    int m; scanf("%d",&m);
    while(m--) {
        int op,x,y;
        scanf("%d%d",&op,&x);
        if(op==1) {
            scanf("%d",&y);
            change(x,y,depth[x]+depth[y]-2*depth[lca(x,y)]+1);
        } else {
            //if(x==2) cout<<t3.query(1,dfn[x])<<"**"<<endl;
            printf("%lld\n",t1.query(1,dfn[x])*dfn[x]*dfn[x]+t2.query(1,dfn[x])-2*dfn[x]*t3.query(1,dfn[x]));
        }
    }
    
    return 0;
}


启发式合并
//n个布丁，有m个颜色
//操作： op1:要把一个颜色的布丁全部变为另一种颜色 op2:询问连续的颜色段个数
#include<iostream> 
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1000010,M=1000010; // 节点 操作数
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qmi(ll m,ll k, ll p=mod){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;}
ll inv(ll a){return qmi(a,mod-2);}
int n,m;
int h[M],e[N],ne[N],idx; 
int color[N],sz[M],p[M]; // 颜色 大小 映射
int ans;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    sz[a]++;
}
void merge(int& x,int &y){
    if(x==y)return;
    if(sz[x]>sz[y])swap(x,y);
    //段数更新
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        ans-=(color[j-1]==y)+(color[j+1]==y);
    }
    //合并
    for(int i=h[x];~i;i=ne[i]){
        int j=e[i];
        color[j]=y;
        // 头插法
        if(ne[i]==-1){
            ne[i]=h[y],h[y]=h[x];
            break;
        }
    }
    h[x]=-1;//清空；
    sz[y]+=sz[x],sz[x]=0;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof  h);
    for(int i=1;i<=n;i++){
        scanf("%d",&color[i]);
        if(color[i]!=color[i-1])ans++; //如果与前面不同
        add(color[i],i); //添加到这个颜色下面
    }
    //初始化映射
    for(int i=0;i<M;i++)p[i]=i;
    while(m--){
        int op;scanf("%d",&op);
        if(op==2)printf("%d\n",ans);
        else {
            int x,y;scanf("%d%d",&x,&y);
            merge(p[x],p[y]);
        }   
    }
    return 0;
}



树上启发式合并
dsu on tree
/*
有一棵 n 个结点的以 1 号结点为根的有根树。
每个结点都有一个颜色，颜色是以编号表示的，i号结点的颜色编号为 c_i
如果一种颜色在以 x 为根的子树内出现次数最多，称其在以 x 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
你的任务是对于每一个 i\in[1,n]，求出以 ii 为根的子树中，占主导地位的颜色的编号和。
*/
#include <cstdio>
#include <cstring>
const int maxn = 1e5+5;
struct E
{
    int to,next;
}Edge[maxn<<1];
int tot,Head[maxn];
inline void AddEdge(int u,int v)
{
    Edge[tot].to=v;
    Edge[tot].next=Head[u];
    Head[u]=tot++;
}
int siz[maxn],son[maxn];
void dfs(int u,int f)           //与重链剖分相同的写法找重儿子
{
    siz[u]=1;
    for(int i=Head[u];~i;i=Edge[i].next)
    {
        int v = Edge[i].to;
        if(v==f) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
int col[maxn],cnt[maxn];    //col存放某结点的颜色，cnt存放某颜色在“当前”子树中的数量
long long ans[maxn],sum;    //ans是答案数组，sum用于累加计算出“当前”子树的答案
int flag,maxc;              //flag用于标记重儿子，maxc用于更新最大值
//TODO 统计某结点及其所有轻儿子的贡献
void count(int u,int f,int val)
{
    cnt[col[u]]+=val;//val为正为负可以控制是增加贡献还是删除贡献
    if(cnt[col[u]]>maxc)    //找最大值，基操吧
    {
        maxc=cnt[col[u]];
        sum=col[u];
    }
    else if(cnt[col[u]]==maxc)  //这样做是因为如果两个颜色数量相同那都得算
        sum+=col[u];
    for(int i=Head[u];~i;i=Edge[i].next) //排除被标记的重儿子，统计其它儿子子树信息
    {
        int v = Edge[i].to;
        if(v==f||v==flag) continue; //不能写if(v==f||v==son[u]) continue;
        count(v,u,val);
    }
}
//dsu on tree的板子
void dfs(int u,int f,bool keep)
{
    //* 第一步：搞轻儿子及其子树算其答案删贡献
    for(int i=Head[u];~i;i=Edge[i].next)
    {
        int v = Edge[i].to;
        if(v==f||v==son[u]) continue;
        dfs(v,u,false);
    }
    //* 第二步：搞重儿子及其子树算其答案不删贡献
    if(son[u])
    {
        dfs(son[u],u,true);
        flag = son[u];//标记重儿子
    }
    //* 第三步：暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里
    count(u,f,1);
    flag = 0;   
    ans[u] = sum;
    //* 把需要删除贡献的删一删
    if(!keep)
    {
        count(u,f,-1);
        sum=maxc=0; //这是因为count函数中会改变这两个变量值
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    memset(Head,-1,sizeof(Head));
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",col+i);
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,0);
    dfs(1,0,0);
    for(int i=1;i<=n;i++)
        printf("%I64d ",ans[i]);
    return 0;
}


RMQ
//求解区间最大值
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 200010,M = 18;
int a[N];
int n,m;
int f[N][M];

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>a[i];

    for(int j = 0;j<M;j++){
        for(int i = 1;i+(1<<j)-1<=n;i++)
            if(!j)f[i][j] = a[i];//只有一个数
            else f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }

    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        int len = r-l+1;
        int k = __lg(len);
        cout<< max(f[l][k],f[r-(1<<k)+1][k])<<endl;;
    }
    return 0;
}


平衡树
#include <bits/stdc++.h>
using namespace std;
//注意数据范围，别爆int/注意特殊判断某些情况

const int N=100005,INF=1e8;
int n;
struct Node
{
    int l,r;
    int key,val;
    int cnt,size;//cnt为相同数值点的数目，size为该点子树的数目
}tr[N*4];

int root,idx;

void pushup(int p)
{
    tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;

}

int get_node(int key)
{
    tr[++idx].key=key;
    tr[idx].val=rand();
    tr[idx].cnt=tr[idx].size=1;
    return idx;
}

void build()
{
    get_node(-INF),get_node(INF);
    root=1,tr[1].r=2;//手动建立哨兵
    pushup(root);
}

void zig(int &p)//右旋，因为根节点也会改变所以传入引用
{
    int q=tr[p].l;
    tr[p].l=tr[q].r,tr[q].r=p,p=q;
    pushup(tr[p].r),pushup(p);
}

void zag(int &p)
{
    int q=tr[p].r;
    tr[p].r=tr[q].l,tr[q].l=p,p=q;
    pushup(tr[p].l),pushup(p);
}

void insert(int &p,int key)//更新p之后需要更新原来传过来的位置，故&
{
    if(!p) p=get_node(key);//到达叶节点
    else if(tr[p].key==key) tr[p].cnt++;
    else if(tr[p].key>key){
        insert(tr[p].l,key);
        if(tr[tr[p].l].val>tr[p].val) zig(p);//可能不满足堆的性质
    }
    else{
        insert(tr[p].r,key);
        if(tr[tr[p].r].val>tr[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p,int key)
{
    if(!p) return ;
    if(tr[p].key==key){
        if(tr[p].cnt>1) tr[p].cnt--;
        else if(tr[p].l||tr[p].r){//不是叶节点
            if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
            {
                zig(p);//右旋，与右儿子交换，同时p发生变化
                remove(tr[p].r,key);//此处的tr[p].r就是要删除的点
            }else
            {
                zag(p);
                remove(tr[p].l,key);
            }
            
        }
        else p=0;
    }
    else if(tr[p].key>key) remove(tr[p].l,key);
    else remove(tr[p].r,key);

    pushup(p);
}

int get_rank_by_key(int p,int key)//通过数值找排名
{
    if(!p) return 0;
    if(tr[p].key==key) return tr[tr[p].l].size+1;
    if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);
    return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}

int get_key_by_rank(int p,int rank)
{
    if(!p) return INF;
    if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;
    return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}

int get_prev(int p,int key)//找到严格小于key的最大值
{
    if(!p) return -INF;
    if(tr[p].key>=key) return get_prev(tr[p].l,key);
    return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_next(int p,int key)
{
    if(!p) return INF;
    if(tr[p].key<=key) return get_next(tr[p].r,key);
    return min(tr[p].key,get_next(tr[p].l,key));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    build();
    cin >>n;
    while(n--){
        int opt,x;
        cin >>opt>>x;
        if(opt==1) insert(root,x);
        else if(opt==2) remove(root,x);
        else if(opt==3) cout <<get_rank_by_key(root,x)-1<<endl;//此处'+/-1'是因为哨兵的存在
        else if(opt==4) cout <<get_key_by_rank(root,x+1)<<endl;
        else if(opt==5) cout<<get_prev(root,x)<<endl;
        else cout <<get_next(root,x)<<endl;
    }

    return 0;
}


点分治
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int p[N], q[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa)  // 求子树大小
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
        if (e[i] != fa)
            res += get_size(e[i], u);
    return res;
}

int get_wc(int u, int fa, int tot, int& wc)  // 求重心
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int& qt)
{
    if (st[u]) return;
    q[qt ++ ] = dist;
    for (int i = h[u]; ~i; i = ne[i])
        if (e[i] != fa)
            get_dist(e[i], u, dist + w[i], qt);
}

int get(int a[], int k)
{
    sort(a, a + k);
    int res = 0;
    for (int i = k - 1, j = -1; i >= 0; i -- )
    {
        while (j + 1 < i && a[j + 1] + a[i] <= m) j ++ ;
        j = min(j, i - 1);
        res += j + 1;
    }
    return res;
}

int calc(int u)
{
    if (st[u]) return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;  // 删除重心

    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt);
        for (int k = 0; k < qt; k ++ )
        {
            if (q[k] <= m) res ++ ;
            p[pt ++ ] = q[k];
        }
    }
    res += get(p, pt);

    for (int i = h[u]; ~i; i = ne[i]) res += calc(e[i]);
    return res;
}

int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        memset(st, 0, sizeof st);
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < n - 1; i ++ )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c), add(b, a, c);
        }

        printf("%d\n", calc(0));
    }

    return 0;
}
